// 解题思路：
// 题目要求：给定一个整数 n，如果 n 是偶数，n 可以执行 / 2 操作，如果 n 是奇数，可以执行 + 1 或者 - 1 操作
// 贪心的策略：能除以 2 则除以 2，不能除以 2 则考虑通过 + 1 或者 - 1，让它后续能除以更多 2
// 如果 n 是偶数就直接 / 2;
// 如果 n 是奇数，判断一下 n 的二进制形式的尾数，如果是 ......01，则直接 - 1，因为减完后后面的 0 会多，方便除以2（右移）
// 如果尾数是 ......11，直接 + 1，因为加完后的 1 都会变为 0，方便除以2（右移）

// 解法 2: 记忆化搜索
// 如果 n 是偶数，就计算 dfs(n / 2) + 1
// 如果 n 是奇数，就计算 min(dfs(n + 1), dfs(n - 1)) + 1
// 因为过程中会出现重复计算，因此需要建一个备忘录，进行记忆化搜索
// 备忘录采用哈希表的形式，因为 n 的取值范围是正整数的范围

// 细节：
// 过程中如果出现 + 1 的操作，n 是有可能会超过正整数的范围的，因此最好是转化成 long 类型，再进行计算，防止越界

import java.util.HashMap;
import java.util.Map;

public class Solution {
    public int integerReplacement1(int n) {
        int ret = 0;
        long m = n;

        while(m != 1){
            if(m % 2 == 0){
                m /= 2;
            }else{
                if(m % 4 == 1 || m == 3){
                    m--;
                }else {
                    m++;
                }
            }
            ret++;
        }

        return ret;
    }

    Map<Long, Integer> hash = new HashMap<>();

    public int integerReplacement2(int n) {
        return dfs(n);
    }
    public int dfs(long n){
        if(n == 1) return 0;

        if(hash.containsKey(n)){
            return hash.get(n);
        }

        if(n % 2 == 0){
            int t = dfs(n / 2) + 1;
            hash.put(n, t);
            return t;
        }else{
            int t1 = dfs(n + 1) + 1;
            int t2 = dfs(n - 1) + 1;

            int ret = Math.min(t1, t2);
            hash.put(n, ret);

            return ret;
        }
    }
}
